package com.company.algo.stack;

import java.util.Stack;

/**
 * 将 pushed 队列中的每个数都 push 到栈中，同时检查这个数是不是 popped 序列中下一个要 pop 的值，如果是就把它 pop 出来。
 * 最后，检查不是所有的该 pop 出来的值都是 pop 出来了。
 */
public class validate_stack_sequences {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int N = pushed.length;
        Stack<Integer> stack = new Stack<>();
        int j  = 0;
        for(int x:pushed){
            stack.push(x);
            while (!stack.isEmpty() && j<N && stack.peek() == popped[j]){
                stack.pop();
                j++;
            }
        }
        return j==N;
    }

}
